package com.itheima.arithmetic.array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class MaxValue {


    public static void main(String[] args) {

       // System.out.println(maxValue(new int[] {4,1, 8, 1, -2, -1}));
       // System.out.println(Arrays.toString(getIndex(new int[] {4, 1, 8, 1, -2, -1}, 12)));
        //System.out.println(Arrays.toString(twoPoint(new int[] {-2, -1, 1, 4, 5, 8}, 12)));
//        System.out.println(getN(10));
//        System.out.println(calucate(10));
//        System.out.println(twoPoint(10));
        System.out.println(coins(1));
    }

    /**
     * 整数数组中三个数的最大乘积
     */
    private static int maxValue(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return Math.max(nums[0]*nums[1]*nums[n-1], nums[n-1]*nums[n-2]*nums[n-3] );
    }

    /**
     * 输入一个目标数, 找出在数组中两个相加数的下标
     */
//    private static int[] getIndex(int[] nums, int target) {
//        Map<Integer, Integer> map = new HashMap<>();
//
//        for (int i = 0; i < nums.length; i++) {
//            if (map.containsKey(target - nums[i])) {
//                return new int[] {map.get(target - nums[i]) ,i};
//            }
//            map.put(nums[i], i);
//        }
//
//        return new int[]{};
//    }

    /**
     * 输入一个目标数, 找出在数组中两个相加数的下标
     * 双指针--最优解 (前提是有序)
     */
    private static int[] twoPoint(int[] nums, int target){
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                return new int[]{left, right};
            } else if (nums[left] + nums[right] < target) {
                // 左指针右移
                left ++;
            } else {
                // 右指针左移
                right --;
            }
        }
        return new int[]{};
    }

    /**
     * 求斐波那锲数列第N位的值
     * 斐波那锲数列: 0,1,1,2,3,5,8...
     * 每一位的值等于前两位数之和, 前两位固定
     */
    private static int getN(int num){
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        return getN(num - 1) + getN(num -2);
    }

    /**
     * 去重递归: 求斐波那锲数列第N位的值
     */
    private static int calucate(int num){
        int[] arr = new int[num + 1];
        return recuse(arr, num);
    }

    private static int recuse(int[] arr, int num) {
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        if (arr[num] != 0) {
            return arr[num];
        }
        arr[num] = recuse(arr, num -1) + recuse(arr, num - 2);
        return arr[num];
    }

    /**
     * 双指针算法:求斐波那锲数列第N位的值
     */
    private static int twoPoint(int num){
        int left = 0, right = 1;
        if (num == 0) {
            return left;
        }
        if (num == 1) {
            return right;
        }

        for (int i = 2; i <= num; i++) {
            int sum = left + right;
            left = right;
            right = sum;
        }

        return right;
    }

    /**
     * n个硬币能放多少行
     *   @
     * @  @
     * @ @ @
     * @ @ @ @
     * ...
     */
    private static int coins(int n) {
        for (int i = 1; i <= n; i++) {
            n = n - i;
            if (n <= i) {
                return i;
            }
        }
        return 0;
    }
}
